package com.lw.leetcode.binary.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * binary
 * 1268. 搜索推荐系统
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/10 20:41
 */
public class SuggestedProducts {


    public static void main(String[] args) {
        SuggestedProducts test = new SuggestedProducts();

        String[] arr = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
        String str = "mouse";

        List<List<String>> lists = test.suggestedProducts(arr, str);
        System.out.println(lists);
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        int length = searchWord.length();
        List<List<String>> all = new ArrayList<>(length);
        Arrays.sort(products);
        int l = products.length;
        for (int i = 1; i <= length; i++) {
            String s = searchWord.substring(0, i);
            List<String> list = new ArrayList<>(3);
            int index = find(products, s);
            if (index != -1) {
                int end = Math.min(index + 3, l);
                for (int j = index; j < end; j++) {
                    if (products[j].startsWith(s)) {
                        list.add(products[j]);
                    } else {
                        break;
                    }
                }
            }
            all.add(list);
        }
        return all;
    }

    private int find(String[] products, String t) {
        int end = products.length - 1;
        int st = 0;
        if (products[end].compareTo(t) < 0) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int compare = products[m].compareTo(t);
            if (compare >= 0) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }


}
